COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.if false then begin "notes"
C00003 00003	.s(COMPUT,COMPUTABILITY)
C00004 00004	.ss(cbneval,A Call-by-name LISP interpreter.)
C00012 00005	.ss(noncomput,Non-computability.)
C00023 ENDMK
C⊗;
.if false then begin "notes"

Recfun theory  LIT...
Connection with lambda calculus?

.end "notes"
.s(COMPUT,COMPUTABILITY)

.ss(cbneval,A Call-by-name LISP interpreter.)

	Except for speed and memory size all present day stored program
computers are equivalent in what computations they can do.  A program
written for one computer can be translated to run on another.  Indeed, 
one can write a simulator for one computer to run on another.  To put it
in commercial terms, no computer manufacturer can advertise that his machine
can do calculations impossible on the machine made by his competitors.

	This is well known intuitively, and the first mathematical theorem
of this kind was proved by A.M. Turing (1936), who defined a primitive kind
of computer now called a Turing machine, and showed how to make a universal
machine that could do any computation done by any Turing machine when given
a description of the machine to be simulated and the initial tape of the
computation to be imitated.

	In LISP the function ⊗eval, defined in Chapter_{SECTION READIN}
({eqn evall!!}) is a universal LISP function in the
sense that any computation done by any LISP function can be done by
⊗eval when ⊗eval is given suitable arguments.


	The way ⊗eval handles arguments corresponds to the call-by-value
method of parameter passing in ALGOL and similar languages.  There is also
a form of ⊗eval that corresponds to call-by-name.
The practical difference between call-by-value and call-by-name is that
sometimes a function doesn't need all its arguments, because the values
of some arguments may make the evaluation of others unnecessary.  A trivial
example is that if ⊗x is 0, then the value of the product ⊗xy can be
determined without evaluating ⊗y.  Other examples involve conditional
expressions.  In call-by-value, a subfunction is given the values of
its arguments, while in call-by-name, it is given the location of program
for computing them and can decide which it wants to compute.  If this
were all there is to say, call-by-name would clearly be superior.
However, in straightforward call-by-name, it can happen that an
argument that is used in two different places is computed twice, and
there are other problems.  LISP uses call-by-value, perhaps mainly
for historical reasons, but it also has some advantages.

	Here is a call-by-name ⊗eval called ⊗neval: 
.begin nofill turnon "∂"
.n←8

∂(n)  ⊗⊗	neval[e, a] ← ⊗
∂(n)  ⊗⊗	qif qat e qthen⊗
∂(n)  ⊗⊗		[qif e = qT  qthen qT⊗
∂(n)  ⊗⊗		qelse qif e = qNIL qthen qNIL⊗
∂(n)  ⊗⊗		qelse qif numberp e qthen e⊗
∂(n)  ⊗⊗		qelse neval[qad assoc[e, a], qdd assoc[e, a]]]⊗
∂(n)  ⊗⊗	qelse qif qat qa e qthen⊗
∂(n)  ⊗⊗		[qif qa e = $CAR qthen qa neval[qad e, a]⊗
∂(n)  ⊗⊗		qelse qif qa e = $CDR qthen qd neval[qad e, a]⊗
!fcnneval& ∂(n)  ⊗⊗		qelse qif qa e = $CONS qthen neval[qad e, a] . neval[qadd e, a]⊗
∂(n)  ⊗⊗		qelse qif qa e = $ATOM qthen qat neval[qad e, a]⊗
∂(n)  ⊗⊗		qelse qif qa e = $EQ qthen neval[qad e, a] = neval[qadd e, a]⊗
∂(n)  ⊗⊗		qelse qif qa e = $QUOTE qthen qad e⊗
∂(n)  ⊗⊗		qelse qif qa e = $COND qthen nevcon[qd e, a]⊗
∂(n)  ⊗⊗		qelse qif qa e = $LIST qthen mapcar[qd e, λx: neval[x, a]]⊗
∂(n)  ⊗⊗		qelse neval[qd assoc[qa e, a] . qd e, a]]⊗
∂(n)  ⊗⊗	qelse qif qaa e = $LAMBDA qthen neval[qadda e, nprup[qada e, qd e,  a]]⊗
∂(n)  ⊗⊗	qelse qif qaa e = $LABEL qthen neval[qadda e . qd e, [qada e . qa e] . a]⊗, 
.end

where the auxiliary function ⊗nevcon is given by

!fcnnevcond& ⊗⊗⊗nevcon[u, a] ← qif neval[qaa u, a] qthen neval[qada u, a] qelse nevcon[qd u, a]⊗.

and ⊗nprup is

!fcnnprup& ⊗⊗⊗nprup[u, v,a] ← qif qn u qthen a qelse [qa u . [qa v . a]] . nprup[qd u, qd v,a]⊗.

	The difference between ⊗eval and ⊗neval is only in two terms.
⊗eval evaluates a variable by looking it up on the association list whereas
⊗neval looks it up on the association list and evaluates the result
in the context in which it was put on the association list.
Correspondingly, when a λ-expression is encountered, ⊗eval forms a new
association list by pairing the values of the arguments with the variables
bound by the λ and putting the new pairs in front of the old association list, 
whereas ⊗neval pairs the arguments themselves with the
variables and puts them on the front of the association list.  The function
⊗neval also saves the current association list with each variable on the 
association list, so that the variables can be evaluated in the correct context.
In most cases they give the same result with the same work, but ⊗neval 
gives a result for some functions of several arguments for
which ⊗eval loops.  An example is
obtained by evaluating ⊗⊗F[2, 1]⊗ where ⊗F is defined by

⊗⊗⊗F[x, y] ← qif x=0 qthen 0 qelse F[x-1, F[y-2, x]]⊗.

	Vuillemin [1973] showed that if a function is ⊗strict, never
has a defined value unless all arguments have a defined value, then
call-by-name and call-by-value always give the same result.
.SKIP 
.cb Exercises

1. Write ⊗neval and the necessary auxiliary functions in list
form, and try them out on some examples.



.ss(noncomput,Non-computability.)

	Some LISP calculations run on indefinitely.  The most trivial
case occurs if we make the recursive definition

!fcnloop&forever ⊗⊗⊗loop x ← loop x		⊗

and attempt to compute ⊗⊗loop[x]⊗ for any ⊗x whatsoever.  Don't
dismiss this example just because no-one would
write such an obviously useless
function definition.  There is a sense in which it is the
"zero" of a large class of non-terminating function definitions, and, 
as the Romans experienced but never learned, leaving zero out of the number
system is a mistake.

	Nevertheless, in most programming, non-terminating calculations are
the results of errors in defining functions.  Therefore, it would be
useful to be able to tell whether a function definition gives a
result for all arguments.  In fact, it would be useful to be able to tell
whether a function will terminate for a single argument.  Let us make
this goal more precise.

	Suppose that ⊗f is a LISP function and ⊗a is an S-expression, 
and we would like to know whether the computation of ⊗f[a] terminates.
Suppose ⊗f is represented by the S-expression ⊗f* in internal
notation.  Then the S-expression $$(⊗f* (QUOTE ⊗⊗a⊗))$
represents ⊗f[a].  Define the function ⊗term by giving
⊗term[e] the value qtrue if ⊗e is an S-expression of the
form $$(⊗f* (QUOTE ⊗⊗a⊗))$ for which ⊗f[a] terminates and qfalse otherwise.
We now ask whether ⊗term is a LISP function, i.e. can it be constructed
from ⊗car, ⊗cdr, ⊗cons, ⊗atom,  and ⊗eq using ⊗λ, ⊗label, and
conditional expressions?  Well, it can't, as we shall shortly prove, 
and this means that it is not ⊗computable whether a LISP calculation
terminates, since if ⊗term were computable by any computer or in any
recognized sense, it could be represented as a LISP function.  Here is the
proof:

	Consider the function ⊗terma defined from ⊗term by

!fcnterma& ⊗⊗⊗terma u ← qif term list[u, list[$QUOTE, u]] qthen loop u qelse qtrue⊗, 

and suppose that ⊗f is a LISP function and that ⊗f* is its
S-expression representation.  What is ⊗terma ⊗f* ?
Well ⊗terma ⊗f* tells us whether the computation of ⊗f[f*] 
terminates, and it tells us this by going into a loop if ⊗f[f*] 
terminates and giving qtrue otherwise.  Now if ⊗term were
a LISP function, then ⊗terma would also be a LISP function.  Indeed if
⊗term were represented by the S-expression ⊗term*, then
⊗terma would be represented by the S-expression

!fcntermastar& ⊗⊗⊗terma*⊗ = $$(LAMBDA (U) (COND ((⊗term* (LIST U (LIST (QUOTE QUOTE) U))) (LOOP U)) (T T)))$.

Now consider ⊗terma[terma*].   According to the definition of ⊗terma, 
this will tell us whether ⊗terma[terma*] is defined, i.e. it tells
about itself.  However, it gives this answer in a contradictory way; namely
⊗terma[terma*] looping tells us that ⊗terma[terma*] terminates, 
and ⊗terma[terma*] being qtrue tells us that ⊗terma[terma*] 
doesn't terminate.  This contradiction tells us that ⊗term is not a
LISP function, and there is no general procedure for telling whether
a LISP calculation terminates.

	The above result does not exclude LISP functions that tell whether
LISP calculations terminate.  It just excludes perfect ones.  Suppose
we have a function ⊗t that sometimes says calculations terminate, 
sometimes says they don't terminate, and sometimes runs on indefinitely.
We shall further assume that when ⊗t gives an
answer it is always right.  Given such a function we can improve it a bit
so that it will always give the right answer when the calculation it is
asked about terminates.  This is done by mixing the computation of ⊗t[e] 
with a computation of ⊗⊗eval[e,_qNIL]⊗ doing the computations
alternately.  If the ⊗⊗eval[e,_qNIL]⊗ computation ever terminates, 
then the new function asserts termination.

	Given such a ⊗t, we can always find a calculation that
does not terminate but ⊗t doesn't say so.  The construction is just like that
used in the previous proof.  Given ⊗t, we construct

!fcnta&  ⊗⊗⊗ta u ← qif t list[u, list[$QUOTE, u]] qthen loop u qelse qtrue⊗, 

and then we consider ⊗ta[ta*].  If this had the value qtrue, 
then it wouldn't terminate so therefore it doesn't terminate but is
not one of those expressions which ⊗t decides.  Thus for any
partial decider we can find a LISP calculation which doesn't terminate
but which the decider doesn't decide.
This can in turn be used to get a slightly better decider, namely

!fcntq1& ⊗⊗⊗tq1[e] ← qif e = ta* qthen $DOESN'T-TERMINATE  qelse t[e]⊗.

.turnon "↓"
Of course, ⊗⊗t⊗%41%* isn't much better than ⊗t, since it can decide
only one more computation, but we can form ⊗⊗t⊗%42%* by applying the same
process, and so forth.  In fact, we can even form ⊗⊗t⊗%8↓w%* which
decides all the cases decided by any ⊗⊗t⊗%4n%*.  This can be further
improved by the same process, etc.  How far can we go?  The answer is
technical; namely, the improvement process can be carried out any
recursive ordinal number of times.

	Unfortunately, this kind of improvement seems to be superficial, 
since none of the new computations proved not to terminate are likely
to be of practical interest.
.SKIP
.cb Exercises

1. Write a function that gives ⊗⊗t⊗%4n+1%* in terms of ⊗⊗t⊗%4n%*.

2. Write a function that gives ⊗⊗t⊗%8↓w%* in terms of ⊗t. 

3. If you know about Turing machines, write a LISP function to
simulate an arbitrary Turing machine given a description of the
machine in some convenient notation.

4. Write a LISP function that will translate a Turing machine
description into a LISP function that will do the same computation.

5. If you really like Turing machines, write a description of
a Turing machine that will interpret LISP internal notation.
.turnoff

.IF FALSE THEN BEGIN
A draft of another exercise

6.  A LISP predicate  ⊗term is called a termination  tester if
for any  S-expression ⊗e, ⊗term[e] = $T if  and only if the LISP
evaluation of  ⊗e  terminates; otherwise  ⊗term[e] = $F  or  is
undefined.   Thus we must have  ⊗term[$(CAR (QUOTE (A)))] = $T, and
%2term[%1((LABEL FOO (LAMBDA (X) (FOO X))) NIL)] may have the value $F 
or  may   be  undefined.      Let  ⊗term*   be  the   S-expression
representation of ⊗term. 

	Write a LISP function ⊗bad such that for any termination
tester ⊗term, ⊗bad[term*] is defined, but ⊗term[bad[term*]] 
is undefined.  Show that your ⊗bad works.

Hint: A two line answer is possible using ⊗subst and the function
⊗⊗quine[x] = subst[x,$$X,(X (QUOTE X))$]⊗. 
.END